// 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

// 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

//  

// 示例 1：

// 输入：n = 12
// 输出：3 
// 解释：12 = 4 + 4 + 4

class Solution {
    public int numSquares(int n) {
        //使用完全背包算法，并将空间维度从二维降至一维
        int[]nums = new int[n+1];
        Arrays.fill(nums,0X3f3f3f3f);//0x3f3f3f3f表示一个最大值
        nums[0] = 0;
        //以可以进行遍历的完全平方数为维度进行遍历
        for(int i=1;i*i<=n;i++)
        {
            int x = i*i;
            for(int j =x;j<=n;j++)
            {
                nums[j]=Math.min(nums[j],nums[j-x]+1);//从小到大进行遍历
            }
        }
        return nums[n];
    }
}
